/**
 * 版权所有 2009-2012山东新北洋信息技术股份有限公司
 * 保留所有权利。
 */
package com.linyaonan.leetcode.medium._515;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 *
 * 您需要在二叉树的每一行中找到最大的值。
 *
 * 示例：
 *
 * 输入:
 *
 *           1
 *          / \
 *         3   2
 *        / \   \
 *       5   3   9
 *
 * 输出: [1, 3, 9]
 *
 *
 * @ProjectName: leetcode
 * @Package: com.linyaonan.leetcode.medium._515
 * @ClassName: FindLargestValue
 * @Author: linyaonan
 * @Date: 2020/1/20 10:39
 */
public class FindLargestValue {
    public List<Integer> largestValues(TreeNode root) {
        Queue<TreeNode> node = new LinkedList<>();
        Queue<Integer> indexs = new LinkedList<>();
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        HashMap<Integer, Integer> save = new HashMap<>();
        node.add(root);
        indexs.add(0);
        save.put(0, root.val);
        while (!node.isEmpty()) {
            TreeNode remove = node.poll();
            Integer index = indexs.poll();
            index++;
            if (remove.left != null) {
                node.add(remove.left);
                indexs.add(index);
                save.put(index, Math.max(save.getOrDefault(index, Integer.MIN_VALUE), remove.left.val));
            }
            if (remove.right != null) {
                node.add(remove.right);
                indexs.add(index);
                save.put(index, Math.max(save.getOrDefault(index, Integer.MIN_VALUE), remove.right.val));
            }
        }
        for (int i = 0; i < save.size(); i++) {
            result.add(save.get(i));
        }
        return result;
    }
}
